package com.tianyuan.test1;
//二分查找
/**
 * 二分查找-I
 * @package com.tianyuan.test1
 * @copyright 甜圆
 * 请实现无重复数字的升序数组的二分查找
 *
 * 给定一个元素升序的、无重复数字的整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标（下标从0
 * 开始），否则返回-1
 *
 * 数据范围:0≤len(nums)≤ 2x10的 5次方，数组中任意值满足|val|≤10的9次方
 */
import java.util.*;

public class Solution {
    /**
     * 二分查找实现（适用于升序、无重复元素的数组）
     * @param nums 升序排列的无重复整型数组
     * @param target 要查找的目标值
     * @return 目标值在数组中的下标，若不存在则返回-1
     */
    public int search (int[] nums, int target) {
        // 定义左边界指针，初始指向数组第一个元素（下标0）
        int left = 0;
        // 定义右边界指针，初始指向数组最后一个元素
        int right = nums.length - 1;
        // 中间位置指针（用于二分比较）
        int mid;

        // 循环条件：左边界 <= 右边界（当左右边界交叉时表示查找结束）
        while (left <= right) {
            // 计算中间位置（避免直接(left+right)可能导致的整数溢出，等价于(left+right)/2）
            mid = left + (right - left) / 2;

            // 情况1：中间元素等于目标值，直接返回中间位置（找到目标）
            if (nums[mid] == target) {
                return mid;
            }
            // 情况2：目标值小于中间元素，说明目标在左半部分
            else if (target < nums[mid]) {
                // 收缩右边界到中间位置左边（因为中间元素已排除）
                right = mid - 1;
            }
            // 情况3：目标值大于中间元素，说明目标在右半部分
            else {
                // 收缩左边界到中间位置右边（因为中间元素已排除）
                left = mid + 1;
            }
        }

        // 循环结束仍未找到目标值，返回-1
        return -1;
    }







    public static void main(String[] args) {
        Solution solution = new Solution();

        // 示例1测试
        int[] nums1 = {-1, 0, 3, 4, 6, 10, 13, 14};
        int target1 = 13;
        int result1 = solution.search(nums1, target1);
        System.out.println("示例1返回值: " + result1); // 预期6

        // 示例2测试
        int[] nums2 = {};
        int target2 = 3;
        int result2 = solution.search(nums2, target2);
        System.out.println("示例2返回值: " + result2); // 预期-1

        // 示例3测试
        int[] nums3 = {-1, 0, 3, 4, 6, 10, 13, 14};
        int target3 = 2;
        int result3 = solution.search(nums3, target3);
        System.out.println("示例3返回值: " + result3); // 预期-1
    }
}
